package com.shm.leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * 301. 删除无效的括号
 * 给你一个由若干括号和字母组成的字符串 s ，删除最小数量的无效括号，使得输入的字符串有效。
 *
 * 返回所有可能的结果。答案可以按 任意顺序 返回。
 *
 *
 *
 * 示例 1：
 *
 * 输入：s = "()())()"
 * 输出：["(())()","()()()"]
 * 示例 2：
 *
 * 输入：s = "(a)())()"
 * 输出：["(a())()","(a)()()"]
 * 示例 3：
 *
 * 输入：s = ")("
 * 输出：[""]
 *
 *
 * 提示：
 *
 * 1 <= s.length <= 25
 * s 由小写英文字母以及括号 '(' 和 ')' 组成
 * s 中至多含 20 个括号
 * @author SHM
 */
public class RemoveInvalidParentheses {
    List<String> res = new ArrayList<>();

    /**
     * 背景知识
     * 有效的「括号」：题目输入的字符串由一系列「左括号」和「右括号」组成，但是有一些额外的括号，使得括号不能正确配对。对于括号配对规则如果还不太清楚的读者，可以先完成问题「20. 有效的括号」。
     *
     * 可以一次遍历计算出多余的「左括号」和「右括号」：
     * 根据括号匹配规则和根据求解「22. 括号生成」的经验，我们知道：如果当前遍历到的「左括号」的数目严格小于「右括号」的数目则表达式无效。因此，我们可以遍历一次输入字符串，统计「左括号」和「右括号」出现的次数。
     *
     * 当遍历到「左括号」的时候：
     * 「左括号」数量加 11。
     * 当遍历到「右括号」的时候：
     * 如果此时「左括号」的数量不为 00，因为「右括号」可以与之前遍历到的「左括号」匹配，此时「左括号」出现的次数 -1−1；
     * 如果此时「左括号」的数量为 00，「右括号」数量加 11。
     * 通过这样的计数规则，得到的「左括号」和「右括号」的数量就是各自最少应该删除的数量。
     *
     * 方法一：回溯 + 剪枝
     * 思路与算法
     *
     * 题目让我们删除括号使得剩下的括号匹配，要求我们删除最少的括号数，并且要求得到所有的结果。我们可以使用回溯算法，尝试遍历所有可能的去掉非法括号的方案。
     *
     * 首先我们利用括号匹配的规则求出该字符串 ss 中最少需要去掉的左括号的数目 \textit{lremove}lremove 和右括号的数目 \textit{rremove}rremove，然后我们尝试在原字符串 ss 中去掉 \textit{lremove}lremove 个左括号和 \textit{rremove}rremove 个右括号，然后检测剩余的字符串是否合法匹配，如果合法匹配则我们则认为该字符串为可能的结果，我们利用回溯算法来尝试搜索所有可能的去除括号的方案。
     *
     * 在进行回溯时可以利用以下的剪枝技巧来增加搜索的效率：
     *
     * 充分利用括号左右匹配的特点（性质），因此我们设置变量 \textit{lcount}lcount 和 \textit{rcount}rcount，分别表示在遍历的过程中已经用到的左括号的个数和右括号的个数，当出现 \textit{lcount} < \textit{rcount}lcount<rcount 时，则我们认为当前的字符串已经非法，停止本次搜索。
     * 我们从字符串中每去掉一个括号，则更新 \textit{lremove}lremove 或者 \textit{rremove}rremove，当我们发现剩余未尝试的字符串的长度小于 \textit{lremove} + \textit{rremove}lremove+rremove 时，则停止本次搜索。
     * 当 \textit{lremove}lremove 和 \textit{rremove}rremove 同时为 00 时，则我们检测当前的字符串是否合法匹配，如果合法匹配则我们将其记录下来。
     * 由于记录的字符串可能存在重复，因此需要对重复的结果进行去重，去重的办法有如下两种：
     *
     * 利用哈希表对最终生成的字符串去重。
     * 我们在每次进行搜索时，如果遇到连续相同的括号我们只需要搜索一次即可，比如当前遇到的字符串为 \texttt{"(((())"}"(((())"，去掉前四个左括号中的任意一个，生成的字符串是一样的，均为 \texttt{"((())"}"((())"，因此我们在尝试搜索时，只需去掉一个左括号进行下一轮搜索，不需要将前四个左括号都尝试一遍。
     *
     * 复杂度分析
     *
     * 时间复杂度：O(n \times 2^n)O(n×2
     * n
     *  )，其中 nn 为字符串的长度。考虑到一个字符串最多可能有 2^n2
     * n
     *   个子序列，每个子序列可能需要进行一次合法性检测，因此时间复杂度为 O(n \times 2^n)O(n×2
     * n
     *  )。
     *
     * 空间复杂度：O(n^2)O(n
     * 2
     *  )，其中 nn 为字符串的长度。返回结果不计入空间复杂度，考虑到递归调用栈的深度，并且每次递归调用时需要复制字符串一次，因此空间复杂度为 O(n^2)O(n
     * 2
     *  )。
     *
     * 作者：LeetCode-Solution
     * 链接：https://leetcode-cn.com/problems/remove-invalid-parentheses/solution/shan-chu-wu-xiao-de-gua-hao-by-leetcode-9w8au/
     * @param s
     * @return
     */
    public List<String> removeInvalidParentheses(String s) {
        int lRemove=0,rRemove = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i)=='('){
                lRemove++;
            }else if(s.charAt(i)==')'){
                if (lRemove==0){
                    rRemove++;
                }else{
                    lRemove--;
                }
            }
        }
        helper(s,0,0,0,lRemove,rRemove);
        return res;
    }

    void helper(String s,int start,int lCount,int rCount,int lRemove,int rRemove){
        if(lRemove==0&&rRemove==0){
            if(isValid(s)){
                res.add(s);
            }
            return;
        }

        for (int i = start; i < s.length(); i++) {
            if (i!=start&&s.charAt(i)==s.charAt(i-1)){
                if (s.charAt(i)=='('){
                    lCount++;
                }else if (s.charAt(i)==')'){
                    rCount++;
                }
                continue;
            }
            //如果剩余的字符无法满足去掉的字符数量要求，直接返回
            if (lRemove+rRemove>s.length()-i){
                return;
            }
            //尝试去掉一个左括号
            if (lRemove>0&&s.charAt(i)=='('){
                helper(s.substring(0,i)+s.substring(i+1),i,lCount,rCount,lRemove-1,rRemove);
            }
            //尝试去掉一个右括号
            if (rRemove>0&&s.charAt(i)==')'){
                helper(s.substring(0,i)+s.substring(i+1),i,lCount,rCount,lRemove,rRemove-1);
            }
            if (s.charAt(i)=='('){
                lCount++;
            }else if (s.charAt(i)==')'){
                rCount++;
            }
            //当前右括号的数量大于左括号则非法直接返回
            if (lCount<rCount){
                break;
            }
        }

    }

    boolean isValid(String s){
        int lRemove = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i)=='('){
                lRemove++;
            }else if (s.charAt(i)==')'){
                if (lRemove==0){
                    return false;
                }else {
                    lRemove--;
                }
            }
        }
        return lRemove==0;
    }
}
